package com.algrithom.dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 256. 粉刷房子
 */
public class Solution10 {
    
    private int[][] costs;
    
    private Map<String,Integer> memo;
    
    public static void main(String[] args){
        int[][] costs = new int[][]{{17,2,17},{16,16,5},{14,3,19}};
        Solution10 solution10 = new Solution10();
        System.out.println(solution10.minCost1(costs));
    }
    
    public int minCost1(int[][] costs){
        int len = costs.length;
        for (int i = len - 2; i >= 0; i--) {
            // Total cost of painting the nth house red.
            costs[i][0] += Math.min(costs[i + 1][1],costs[i + 1][2]);
            // Total cost of painting the nth house green.
            costs[i][1] += Math.min(costs[i + 1][0],costs[i + 1][2]);
            // Total cost of painting the nth house blue.
            costs[i][2] += Math.min(costs[i + 1][0],costs[i + 1][1]);
        }
        
        if (costs.length == 0) {
            return 0;
        }
        
        return Math.min(Math.min(costs[0][0],costs[0][1]),costs[0][2]);
    }
    
    public int minCost2(int[][] costs){
        if (costs.length == 0) {
            return 0;
        }
        this.costs = costs;
        this.memo = new HashMap<>();
        return Math.min(paintCost(0,0),Math.min(paintCost(0,1),paintCost(0,2)));
    }
    
    private int paintCost(int n,int color){
        if (memo.containsKey(getKey(n,color))) {
            return memo.get(getKey(n,color));
        }
        int totalCost = costs[n][color];
        if (color == 0) { // Red
            totalCost += Math.min(paintCost(n + 1,1),paintCost(n + 1,2));
        } else if (color == 1) { // Green
            totalCost += Math.min(paintCost(n + 1,0),paintCost(n + 1,2));
        } else { // Blue
            totalCost += Math.min(paintCost(n + 1,0),paintCost(n + 1,1));
        }
        memo.put(getKey(n,color),totalCost);
        
        return totalCost;
    }
    
    private String getKey(int n,int color){
        return n + " " + color;
    }
    
    public int minCostII(int[][] costs){
        int rowLen = costs.length;
        int colLen = costs[0].length;
        int[] previousRow = costs[0];
        for (int i = 1; i < rowLen; i++) {
            int[] currentRow = Arrays.copyOf(costs[i],colLen);
            for (int color = 0; color < colLen; color++) {
                if (color == 0) {
                    currentRow[color] += Arrays.stream(Arrays.copyOfRange(previousRow,1,colLen)).min().orElse(0);
                } else if (color == colLen - 1) {
                    currentRow[color] += Arrays.stream(Arrays.copyOfRange(previousRow,0,colLen - 1)).min().orElse(0);
                } else {
                    currentRow[color] += Math.min(Arrays.stream(Arrays.copyOfRange(previousRow,0,color)).min().orElse(0),
                        Arrays.stream(Arrays.copyOfRange(previousRow,color + 1,colLen)).min().orElse(0));
                }
            }
            previousRow = currentRow;
        }
        return Arrays.stream(previousRow).min().orElse(0);
    }
}